package com.ddshuai.easy;

/**
 * @author ddshuai
 * @version 1.0.0
 * @date 2018/3/29
 * @modify desc
 * @2018/3/29 新增        1.0.0
 * 实现 strStr()。
 * <p>
 * 返回蕴含在 haystack 中的 needle 的第一个字符的索引，如果 needle 不是 haystack 的一部分则返回 -1 。
 * 输入: haystack = "hello", needle = "ll"
 * 输出: 2
 * 输入: haystack = "aaaaa", needle = "bba"
 * 输出: -1
 */
public class StrStr {

    /**
     * 利用队列来处理
     *
     * @param haystack
     * @param needle
     * @return
     */
    public static int strStr(String haystack, String needle) {

        if (haystack == null || needle == null) {
            return 0;
        }
        char[] target = needle.toCharArray();
        char[] source = haystack.toCharArray();

        return indexOf(source, source.length, target, target.length);
    }

    public static void main(String[] args) {

        System.out.println(strStr("mississippi", "issip"));
    }

    /**
     * jdk里面的解法
     *
     * @param source
     * @param sourceCount
     * @param target
     * @param targetCount
     * @return
     */
    static int indexOf(char[] source, int sourceCount,
                       char[] target, int targetCount
    ) {
        //如果子串长度大于源串长度 肯定是不包含 返回-1
        if (0 >= sourceCount) {
            return (targetCount == 0 ? sourceCount : -1);
        }

        if (targetCount == 0) {
            return 0;
        }

        char first = target[0];
        //最大的下标 最坏的情况是匹配的数据再最后面
        int max = (sourceCount - targetCount);

        //在最大值范围下遍历
        for (int i = 0; i <= max; i++) {
            /* 先找到第一个匹配的字符 减少循环次数*/
            if (source[i] != first) {
                while (++i <= max && source[i] != first) {
                    ;
                }
            }

            /* i 肯定小于最大值下标*/
            if (i <= max) {
                int j = i + 1;
                //匹配到之后最后一位的下标
                int end = j + targetCount - 1;
                //遍历直到不相等，或下标超出之后结束
                for (int k = 1; j < end && source[j]
                        == target[k]; j++, k++) {
                    ;
                }
                //相等 说明从i开始与目标串完全匹配上了，返回I的值
                if (j == end) {
                    /* Found whole string. */
                    return i;
                }
            }
        }
        return -1;
    }
}
